package Tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
 *
 * 两棵树重复是指它们具有相同的结构以及相同的结点值。
 *
 * 示例 1：
 *
 *         1
 *        / \
 *       2   3
 *      /   / \
 *     4   2   4
 *        /
 *       4
 * 下面是两个重复的子树：
 *
 *       2
 *      /
 *     4
 * 和
 *
 *     4
 */
public class L652_寻找重复子树 {
    //通过序列化，以及map来实现
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> res = new ArrayList<>();
        if(root == null) return res;
        Map<String,Integer> map = new HashMap<>();//统计某个节点下的序列，以及出现的次数
        rec_path(root,res,map);
        return res;
    }

    String rec_path(TreeNode root, List<TreeNode> res, Map<String, Integer> map){
        if(root == null) return "";

        StringBuilder sb = new StringBuilder(root.val+",");
        sb.append(rec_path(root.left, res, map));
        sb.append(","+rec_path(root.right, res, map));//一定都要给隔开，这里通过","

        String path = sb.toString();
        if(map.get(path) != null && map.get(path) == 1){
            res.add(root);
        }
        map.put(path, map.getOrDefault(path,0) + 1);
        return path;
    }
}
